class Solution(object):
    def hitBricks(self, grid, hits):
        m = len(grid)
        n = len(grid[0])
        p = [i for i in range(m * n)]

        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx > rooty:
                    p[rootx] = rooty
                else:
                    p[rooty] = rootx

        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    if i > 0 and grid[i - 1][j]:
                        union(i * n + j, (i - 1) * n + j)
                    if j > 0 and grid[i][j - 1]:
                        union(i * n + j, i * n + j - 1)
                else:
                    p[i * n + j] = -1
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    if find(i * n + j) >= n:
                        grid[i][j] = 0
        len_hits = len(hits)
        block = [0] * len_hits
        for index, (x, y) in enumerate(hits):
            if grid[x][y]:
                block[index] = 1
                grid[x][y] = 0
        rank = [0] * (m * n)
        p = [i for i in range(m * n)]

        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx > rooty:
                    p[rootx] = rooty
                    rank[rooty] += rank[rootx]
                    if rooty < n and rootx >= n:
                        add = rank[rootx]
                    else:
                        add = 0
                    rank[rootx] = 0

                else:
                    p[rooty] = rootx
                    rank[rootx] += rank[rooty]
                    if rootx < n and rooty >= n:
                        add = rank[rooty]
                    else:
                        add = 0
                    rank[rooty] = 0
            else:
                add = 0
            return add

        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    rank[i * n + j] = 1
                    if i > 0 and grid[i - 1][j]:
                        union(i * n + j, (i - 1) * n + j)
                    if j > 0 and grid[i][j - 1]:
                        union(i * n + j, i * n + j - 1)
                else:
                    p[i * n + j] = -1
        ans = []
        for t in range(len_hits - 1, -1, -1):
            if block[t]:
                x, y = hits[t]
                grid[x][y] = 1
                rank[x * n + y] = 1
                p[x * n + y] = x * n + y
                increase = 0
                if x == 0:
                    increase += 1
                if x > 0 and grid[x - 1][y]:
                    increase += union(x * n + y, (x - 1) * n + y)
                if x < m - 1 and grid[x + 1][y]:
                    increase += union(x * n + y, (x + 1) * n + y)
                if y > 0 and grid[x][y - 1]:
                    increase += union(x * n + y, x * n + y - 1)
                if y < n - 1 and grid[x][y + 1]:
                    increase += union(x * n + y, x * n + y + 1)
                ans.append(max(0, increase - 1))
            else:
                ans.append(0)

        ans.reverse()
        return ans


data = Solution()
grid = [[1, 0, 0, 0], [1, 1, 1, 0]]
hits = [[1, 0]]
print(data.hitBricks(grid, hits))
grid = [[1, 0, 0, 0], [1, 1, 0, 0]]
hits = [[1, 1], [1, 0]]
print(data.hitBricks(grid, hits))
grid = [[1, 0, 1], [1, 1, 1]]
hits = [[0, 0], [0, 2], [1, 1]]
print(data.hitBricks(grid, hits))
